package com.javaDemo.ti;

import java.util.*;

/**
 * 二分查找类算法题详解
 * 
 * @author csy
 * @description 面试中常见的二分查找类算法题的详细解析
 */
public class BinarySearchExamples {

    /**
     * 【二分查找基础】在排序数组中查找元素的第一个和最后一个位置
     * 
     * 问题描述：
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。
     * 找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。
     * 
     * 解题思路详解：
     * 1. 为什么要进行两次二分查找？
     * - 第一次查找第一个位置
     * - 第二次查找最后一个位置
     * 
     * 2. 详细步骤解析：
     * a) 查找第一个位置
     * - 当找到目标值时，继续向左查找
     * - 记录当前位置作为候选结果
     * 
     * b) 查找最后一个位置
     * - 当找到目标值时，继续向右查找
     * - 记录当前位置作为候选结果
     * 
     * 3. 边界处理策略：
     * a) 左边界查找
     * - 当nums[mid] == target时，right = mid - 1
     * - 记录mid作为可能的左边界
     * 
     * b) 右边界查找
     * - 当nums[mid] == target时，left = mid + 1
     * - 记录mid作为可能的右边界
     * 
     * 4. 举例详解：
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 
     * 查找左边界：
     * 1) left=0, right=5, mid=2
     * nums[2]=7 < 8, left=3
     * 2) left=3, right=5, mid=4
     * nums[4]=8 == 8, right=3, 记录4
     * 3) left=3, right=3, mid=3
     * nums[3]=8 == 8, right=2, 记录3
     * 
     * 查找右边界类似...
     * 
     * 时间复杂度：O(log n)
     * 空间复杂度：O(1)
     */
    public static int[] searchRange(int[] nums, int target) {
        int[] result = { -1, -1 };
        if (nums == null || nums.length == 0)
            return result;

        // 查找左边界
        result[0] = findBound(nums, target, true);
        if (result[0] == -1)
            return result;

        // 查找右边界
        result[1] = findBound(nums, target, false);

        return result;
    }

    private static int findBound(int[] nums, int target, boolean isLeft) {
        int left = 0, right = nums.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                result = mid;
                if (isLeft) {
                    right = mid - 1; // 继续向左查找
                } else {
                    left = mid + 1; // 继续向右查找
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }

    /**
     * 【二分查找变体】寻找峰值
     * 
     * 问题描述：
     * 峰值元素是指其值严格大于左右相邻值的元素。
     * 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
     * 
     * 解题思路详解：
     * 1. 为什么可以用二分查找？
     * - 如果mid比右边小，则右边一定有峰值
     * - 如果mid比右边大，则左边一定有峰值
     * 
     * 2. 详细步骤解析：
     * a) 二分查找策略
     * - 比较mid和mid+1的值
     * - 根据比较结果选择区间
     * 
     * b) 区间选择依据
     * - nums[mid] > nums[mid+1]：峰值在左边
     * - nums[mid] < nums[mid+1]：峰值在右边
     * 
     * 3. 正确性证明：
     * a) 如果nums[mid] < nums[mid+1]
     * - 说明mid到mid+1是上升的
     * - 要么mid+1就是峰值
     * - 要么在mid+1右边还有更大的值
     * 
     * 4. 举例详解：
     * 输入：[1,2,1,3,5,6,4]
     * 
     * 1) left=0, right=6, mid=3
     * nums[3]=3 < nums[4]=5，选择右半部分
     * 
     * 2) left=4, right=6, mid=5
     * nums[5]=6 > nums[6]=4，选择左半部分
     * 
     * 3) 返回峰值6的索引5
     * 
     * 时间复杂度：O(log n)
     * 空间复杂度：O(1)
     */
    public static int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[mid + 1]) {
                // 峰值在左边
                right = mid;
            } else {
                // 峰值在右边
                left = mid + 1;
            }
        }

        return left;
    }

    /**
     * 【二分查找应用】搜索二维矩阵
     * 
     * 问题描述：
     * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
     * - 每行的元素从左到右升序排列。
     * - 每行的第一个整数大于前一行的最后一个整数。
     * 
     * 解题思路详解：
     * 1. 为什么可以转化为一维二分查找？
     * - 矩阵是有序的，可以看作一个排序数组
     * - 可以通过下标转换在矩阵中定位
     * 
     * 2. 详细步骤解析：
     * a) 坐标转换
     * - 一维索引转二维行：idx / n
     * - 一维索引转二维列：idx % n
     * 
     * b) 二分查找过程
     * - 在[0, m*n-1]范围内二分
     * - 通过转换得到矩阵中的实际位置
     * 
     * 3. 边界处理：
     * a) 特殊情况
     * - 空矩阵
     * - 空行
     * 
     * 4. 举例详解：
     * 输入：matrix = [
     * [1, 3, 5, 7],
     * [10, 11, 16, 20],
     * [23, 30, 34, 60]
     * ], target = 3
     * 
     * 1) left=0, right=11, mid=5
     * idx=5 -> matrix[1][1]=11 > 3
     * right = 4
     * 
     * 2) left=0, right=4, mid=2
     * idx=2 -> matrix[0][2]=5 > 3
     * right = 1
     * 
     * 3) left=0, right=1, mid=1
     * idx=1 -> matrix[0][1]=3 == 3
     * 返回true
     * 
     * 时间复杂度：O(log(m*n))
     * 空间复杂度：O(1)
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = matrix[mid / n][mid % n];

            if (value == target) {
                return true;
            } else if (value < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试在排序数组中查找元素的第一个和最后一个位置
        System.out.println("=== 查找元素的第一个和最后一个位置测试 ===");
        int[] nums1 = { 5, 7, 7, 8, 8, 10 };
        int target1 = 8;
        int[] range = searchRange(nums1, target1);
        System.out.println("输入数组：" + Arrays.toString(nums1));
        System.out.println("目标值：" + target1);
        System.out.println("结果：" + Arrays.toString(range) + "\n");

        // 测试寻找峰值
        System.out.println("=== 寻找峰值测试 ===");
        int[] nums2 = { 1, 2, 1, 3, 5, 6, 4 };
        int peakIndex = findPeakElement(nums2);
        System.out.println("输入数组：" + Arrays.toString(nums2));
        System.out.println("峰值索引：" + peakIndex);
        System.out.println("峰值：" + nums2[peakIndex] + "\n");

        // 测试搜索二维矩阵
        System.out.println("=== 搜索二维矩阵测试 ===");
        int[][] matrix = {
                { 1, 3, 5, 7 },
                { 10, 11, 16, 20 },
                { 23, 30, 34, 60 }
        };
        int target2 = 3;
        boolean found = searchMatrix(matrix, target2);
        System.out.println("目标值：" + target2);
        System.out.println("是否找到：" + found);
    }
}